﻿class Solution
	2 {
3 public:
	4 int findTargetSumWays(vector<int>&nums, int target)
		5 {
		6 int sum = 0;
		7 for (auto x : nums) sum += x;
		8 int aim = (sum + target) / 2;
		9 // 处理⼀下边界条件
			10 if (aim < 0 || (sum + target) % 2) return 0;
		11 int n = nums.size();
		12 vector<vector<int>> dp(n + 1, vector<int>(aim + 1)); // 建表
		13 dp[0][0] = 1; // 初始化
		14 for (int i = 1; i <= n; i++) // 填表
			15 for (int j = 0; j <= aim; j++)
			16 {
			17 dp[i][j] = dp[i - 1][j];
			18 if (j >= nums[i - 1]) dp[i][j] += dp[i - 1][j - nums[i - 1]];
			19 }
		20 // 返回结果
			21 return dp[n][aim];